package com.leetcode.题库;

import java.util.Arrays;

/**
 * @author 覃国强
 * @date 2022-03-03 18:48
 */
public class 题库_0215_数组中的第K个最大元素 {

  static
  class Solution {
    public int findKthLargest(int[] nums, int k) {

      if (k > nums.length) {
        return 0;
      }

      int[] arr = Arrays.copyOf(nums, k);
      buildMinHeap(arr);

      for (int i = k; i < nums.length; ++i) {
        if (nums[i] > arr[0]) {
          arr[0] = nums[i];
          minHeapify(arr, 0);
        }
      }

      return arr[0];
    }


    private void buildMinHeap(int[] arr) {
      for (int i = (arr.length - 2) / 2; i >= 0; --i) {
        minHeapify(arr, i);
      }
    }

    private void minHeapify(int[] arr, int i) {
      int left = 2 * i + 1;
      int right = 2 * i + 2;
      int target = i;
      if (left < arr.length && arr[left] < arr[target]) {
        target = left;
      }
      if (right < arr.length && arr[right] < arr[target]) {
        target = right;
      }
      if (target != i) {
        swap(arr, i, target);
        minHeapify(arr, target);
      }
    }


    private void swap(int[] nums, int i, int j) {
      int temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
    }
  }

}
